package own.stu.jobgib.playown.alg.solution.backtrack;

import java.util.ArrayList;
import java.util.List;

/*
回文
 */
public class Plalindrome {

    public static void main(String[] args) {
        Plalindrome p = new Plalindrome();
       /* boolean[][] res = p.plalin("aaa");
        printArray(res);
        System.out.println();
        res = p.plalin_ii("aaa");
        printArray(res);*/
//        System.out.println(p.countSubstrings("aba"));

//        System.out.println(p.partition("aab"));
//        System.out.println(p.partition("aaba"));
//        System.out.println(p.partition("abbab"));


//        System.out.println(p.restoreIpAddresses("0000"));
        System.out.println(p.restoreIpAddresses("101023"));
//        System.out.println(p.restoreIpAddresses("25525511135"));
    }

    private static void printArray(boolean[][] res) {
        for (boolean[] r : res) {
            for (boolean b : r) {
                System.out.print(b + ", ");
            }
            System.out.println();
        }
    }

    /**
     * 647. 回文子串
     * 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
     * <p>
     * 回文字符串 是正着读和倒过来读一样的字符串。
     * <p>
     * 子字符串 是字符串中的由连续字符组成的一个序列。
     * <p>
     * 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
     * <p>
     * 示例 1：
     * <p>
     * 输入：s = "abc"
     * 输出：3
     * 解释：三个回文子串: "a", "b", "c"
     */
    public int countSubstrings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        boolean[][] plalin = plalin(s);
        int ans = 0;
        for (boolean[] p : plalin) {
            for (boolean b : p) {
                if (b) ans++;
            }
        }
        return ans;
    }

    private boolean[][] plalin(String s) {
        int n = s.length();
        boolean[][] p = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            p[i][i] = true;
        }

        for (int i = 0; i < n - 1; i++) { // len = 1
            p[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
        }

        for (int len = 2; len < n; len++) {
            for (int i = 0; i < n - len; i++) {
                if (s.charAt(i) == s.charAt(i + len) && p[i + 1][i + len - 1]) {
                    p[i][i + len] = true;
                }
            }
        }
        return p;
    }

    // s[i][j]表示 s[i..j-1]是否是回文串，以生成 回文串的方式来判断，向两端扩展
    private boolean[][] plalin_ii(String s) {
        int n = s.length();
        boolean[][] p = new boolean[n][n];
        char[] cs = s.toCharArray();
        int i, j;
        for (int c = 0; c < n; c++) { // s的子串长度为偶数
            i = j = c;
            while (i >= 0 && j < n && cs[i] == cs[j]) {
                p[i][j] = true;
                i--;
                j++;
            }
        }

        // s的子串长度为奇数，表示以字符中间竖线来向两头扩展, aba len(s) = 3, 中间的竖线有2个
        for (int c = 0; c < n - 1; c++) {
            i = c;
            j = c + 1;
            while (i >= 0 && j < n && cs[i] == cs[j]) {
                p[i][j] = true;
                i--;
                j++;
            }
        }

        return p;
    }

    /**
     * 131. 分割回文串
     * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
     * <p>
     * 回文串 是正着读和反着读都一样的字符串。
     * <p>
     * 示例 1：
     * 输入：s = "aab"
     * 输出：[["a","a","b"],["aa","b"]]
     */
    public List<List<String>> partition(String s) {
        List<List<String>> ans = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return ans;
        }
        char[] cs = s.toCharArray();
        int n = cs.length;
        boolean[][] palin = plalin(s);

        partitionHelper(ans, s, new ArrayList<>(), 0, palin);

        return ans;
    }

    private void partitionHelper(List<List<String>> ans, String s, List<String> list, int startIdx, boolean[][] palin) {
        if (startIdx >= s.length()) {
            ans.add(new ArrayList<>(list));
            return;
        }

        for (int i = startIdx; i < s.length(); i++) { // 重点 startIdx 为分割位置

            if (!palin[startIdx][i]) {
                continue;
            }

            list.add(s.substring(startIdx, i + 1));
            partitionHelper(ans, s, list, i + 1, palin);
            list.remove(list.size() - 1);
        }
    }

    /**
     * 93. 复原 IP 地址
     * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
     * <p>
     * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
     * 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
     * <p>
     * 示例 1：
     * 输入：s = "25525511135"
     * 输出：["255.255.11.135","255.255.111.35"]
     * <p>
     * 示例 2：
     * 输入：s = "0000"
     * 输出：["0.0.0.0"]
     */
    public List<String> restoreIpAddresses(String s) {
        List<String> ans = new ArrayList<>();
        if (s == null || s.length() < 4 || s.length() > 12) {
            return ans;
        }

        restoreIpAddressesHelper(ans, s, 0, new ArrayList<>());

        return ans;
    }

    private void restoreIpAddressesHelper(List<String> ans, String s, int startIdx, List<String> list) {
        if (startIdx >= s.length() || list.size() >= 4) {
            if (list.size() == 4 && startIdx >= s.length())
                ans.add(String.join(".", list));
            return;
        }

        for (int i = startIdx; i < s.length(); i++) {
            if (is0to255(s, startIdx, i)) {
                list.add(s.substring(startIdx, i + 1));
                restoreIpAddressesHelper(ans, s, i + 1, list);
                list.remove(list.size() - 1);
            }
        }
    }

    private boolean is0to255(String s, int l, int r) {
        if (r - l >= 4) {
            return false;
        }
        if (r - l >= 1 && s.charAt(l) == '0') {
            return false;
        }
        Integer v = Integer.valueOf(s.substring(l, r + 1));
        return v >= 0 && v <= 255;
    }
}
